package com.wenhao.leetcode.hard;

/**
 * 题目：https://leetcode-cn.com/problems/minimum-window-substring/
 * 最小覆盖字串
 *
 * @author Wenhao Tong
 * @create 2021-07-09 17:20
 */
public class LeetCode76 {
    public static void main(String[] args) {

    }
    public String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" || s.length() < t.length()) {
            return "";
        }
        int[] need = new int[128];
        int[] have = new int[128];
        for (int i = 0;i < t.length();i++) {
            need[t.charAt(i)]++;
        }
        int left = 0;
        int right = 0;
        int count = 0;
        // 用来记录符合条件的起点和终点
        int lo = 0;
        int hi = s.length() + 1;
        while (right < s.length()) {
            char r = s.charAt(right);
            // 如果当前的字符是不被需要的那么可以直接看下一个字符
            if (need[r] == 0) {
                right++;
                continue;
            }
            // 统计当前在窗口里面的有效的字符的个数
            if (have[r] < need[r]) {
                count++;
            }
            have[r]++;
            right++;
            // 如果当前窗口里面有效字符的个数足够的话，说明此时窗口里已经包含了所有需要的字符
            while (count == t.length()) {
                char l = s.charAt(left);
                // 更新字串的起点和终点
                if (right - left < hi - lo) {
                    lo = left;
                    hi = right;
                }
                if (need[l] == 0) {
                    left++;
                    continue;
                }

                if (have[l] == need[l]) {
                    count--;
                }

                have[l]--;
                left++;
            }
        }
        if (hi == s.length() + 1) {
            return "";
        }
        return s.substring(lo,hi + 1);
    }
}
